package thired.class10_graph;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Class08_Prim {
    public static Set<Edge> primMST(Graph graph){
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>((o1,o2)-> {return o1.value - o2.value;});
        HashSet<Node> nodeSet = new HashSet<>();
        HashSet<Edge> res = new HashSet<>();

       for(Node node : graph.nodes.values()){
          if(!nodeSet.contains(node)){
              nodeSet.add(node);
              priorityQueue.addAll(node.edges);
              while (!priorityQueue.isEmpty()){
                  Edge edge = priorityQueue.poll();
                  Node toNode = edge.to; // 可能的一个新的点
                  if (!nodeSet.contains(toNode)) { // 不含有的时候，就是新的点
                      nodeSet.add(toNode);
                      res.add(edge);
                      priorityQueue.addAll(toNode.edges);
                  }

              }
          }
       }
       return res;
    }
}
